{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Moves to Make Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #binary-indexed-tree #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #树状数组 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minMovesToMakePalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得到回文串的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个只包含小写英文字母的字符串&nbsp;<code>s</code>&nbsp;。</p>\n",
    "\n",
    "<p>每一次 <strong>操作</strong>&nbsp;，你可以选择 <code>s</code>&nbsp;中两个 <strong>相邻</strong>&nbsp;的字符，并将它们交换。</p>\n",
    "\n",
    "<p>请你返回将 <code>s</code>&nbsp;变成回文串的 <strong>最少操作次数</strong>&nbsp;。</p>\n",
    "\n",
    "<p><strong>注意</strong>&nbsp;，输入数据会确保&nbsp;<code>s</code>&nbsp;一定能变成一个回文串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"aabb\"\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "我们可以将 s 变成 2 个回文串，\"abba\" 和 \"baab\" 。\n",
    "- 我们可以通过 2 次操作得到 \"abba\" ：\"a<em><strong>ab</strong></em>b\" -&gt; \"ab<em><strong>ab</strong></em>\" -&gt; \"abba\" 。\n",
    "- 我们可以通过 2 次操作得到 \"baab\" ：\"a<em><strong>ab</strong></em>b\" -&gt; \"<em><strong>ab</strong></em>ab\" -&gt; \"baab\" 。\n",
    "因此，得到回文串的最少总操作次数为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"letelt\"\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "通过 2 次操作从 s 能得到回文串 \"lettel\" 。\n",
    "其中一种方法是：\"lete<em><strong>lt</strong></em>\" -&gt; \"let<em><strong>et</strong></em>l\" -&gt; \"lettel\" 。\n",
    "其他回文串比方说 \"tleelt\" 也可以通过 2 次操作得到。\n",
    "可以证明少于 2 次操作，无法得到回文串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 2000</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li><code>s</code>&nbsp;可以通过有限次操作得到一个回文串。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-moves-to-make-palindrome](https://leetcode.cn/problems/minimum-number-of-moves-to-make-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-moves-to-make-palindrome](https://leetcode.cn/problems/minimum-number-of-moves-to-make-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabb\"', '\"letelt\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = 0\n",
    "        j = len(s)-1\n",
    "        s = [*s]\n",
    "        while i < j:\n",
    "            flag = False\n",
    "            for k in range(j, i, -1):\n",
    "                if s[i] == s[k]:\n",
    "                    flag = True\n",
    "                    while k < j:\n",
    "                        tmp = s[k]\n",
    "                        s[k] = s[k+1]\n",
    "                        s[k+1] = tmp\n",
    "                        k += 1\n",
    "                        res += 1\n",
    "                    j -= 1\n",
    "                    break\n",
    "            if flag == False:\n",
    "                res += len(s)//2 - i\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        now, change = 0, 0\n",
    "        res = 0\n",
    "        while now < n//2:\n",
    "            while s[change] != s[n-1-now] and s[n-1-change] != s[now]:\n",
    "                change += 1\n",
    "                res += 1\n",
    "            if s[change] == s[n-1-now]:\n",
    "                c = s.pop(change)\n",
    "                s = [c] + s\n",
    "            else:\n",
    "                c = s.pop(n-1-change)\n",
    "                s.append(c)\n",
    "            \n",
    "            now += 1\n",
    "            change = now\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n >> 1):\n",
    "            j = s.rindex(s[i])\n",
    "            if j == i: \n",
    "                ans += (n >> 1) - i\n",
    "                s = s[ : i] + s[i + 1:]\n",
    "                n -= 1\n",
    "                j = s.rindex(s[i])\n",
    "            ans += n - 1 - i - j\n",
    "            s = s[ : j ] + s[ j + 1: n - i ]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        alphaPos = defaultdict(deque)\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            alphaPos[s[i]].append(i)\n",
    "        res = 0\n",
    "        for i in range(n//2):\n",
    "            min_swap = 2*n\n",
    "            use = 'a'\n",
    "            for c in alphaPos:\n",
    "                if len(alphaPos[c]) > 1:\n",
    "                    swap = max(0, alphaPos[c][0]-i) + \\\n",
    "                        max(0, n-i-1-alphaPos[c][-1])\n",
    "                    if swap < min_swap:\n",
    "                        min_swap = swap\n",
    "                        use = c\n",
    "            res += min_swap\n",
    "            left = alphaPos[use].pop()\n",
    "            right = alphaPos[use].popleft()\n",
    "            for c in alphaPos:\n",
    "                for i in range(len(alphaPos[c])):\n",
    "                    if alphaPos[c][i] < left:\n",
    "                        alphaPos[c][i] += 1\n",
    "                    if alphaPos[c][i] > right:\n",
    "                        alphaPos[c][i] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        ans, n= 0,len(s)\n",
    "        for i in range(n>>1):\n",
    "            j = s.rindex(s[i])\n",
    "            if j==i:\n",
    "                ans+= (n>>1)-i\n",
    "                s = s[:i]+s[i+1:]\n",
    "                n-=1\n",
    "                j = s.rindex(s[i])\n",
    "            ans += n-1-i-j\n",
    "            s = s[:j]+s[j+1:n-i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n // 2):\n",
    "            j = s.rfind(s[i])\n",
    "            if j == i:\n",
    "                ans += n // 2 - i \n",
    "                s = s[:i] + s[i+1:]\n",
    "                n -= 1\n",
    "                j = s.rfind(s[i])\n",
    "            ans += n - 1 - i - j\n",
    "            s = s[:j] + s[j+1:]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n=len(s)  \n",
    "        ans=c=0\n",
    "        sl=list(s)\n",
    "        for i in range(n//2):\n",
    "            ch=sl[i]\n",
    "            right=n-1-c      \n",
    "            while sl[right]!=ch:\n",
    "                right-=1\n",
    "            #print('right',right,'i',i)\n",
    "            if right==i:\n",
    "                ans+=(n//2-i)  \n",
    "            else:\n",
    "                ans+=(n-1-c-right)   \n",
    "                for j in range(right,n-1-c):\n",
    "                    sl[j],sl[j+1]=sl[j+1],sl[j]\n",
    "                c+=1\n",
    "          #  print(sl)\n",
    "            \n",
    "        return ans     \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        arr_s=list(s)\n",
    "        while i < j:\n",
    "            k = j\n",
    "            while i != k:\n",
    "                if arr_s[i] == arr_s[k]:\n",
    "                    for x in range(k, j):\n",
    "                        arr_s[x],arr_s[x+1]=arr_s[x+1],arr_s[x]\n",
    "                        res += 1\n",
    "                    j -= 1\n",
    "                    break\n",
    "                k -= 1\n",
    "            else:\n",
    "                res += n // 2 - i\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "\n",
    "        ans = 0\n",
    "        left, right = OrderedDict(), OrderedDict()\n",
    "        left_cnt = right_cnt = 0\n",
    "\n",
    "        for i, t in enumerate(s):\n",
    "            if t not in left:\n",
    "                left[t] = []\n",
    "            \n",
    "            if len(left[t]) < cnt[t] // 2:\n",
    "                ans += (i - left_cnt)\n",
    "                left_cnt += 1\n",
    "                left[t].append(left_cnt)\n",
    "            else:\n",
    "                right_cnt += 1\n",
    "                if t not in right:\n",
    "                    right[t] = []\n",
    "                right[t].append(right_cnt)\n",
    "        \n",
    "        if (len(s)) % 2:\n",
    "            for key, val in cnt.items():\n",
    "                if val % 2:\n",
    "                    left_cnt += 1\n",
    "                    if key not in left:\n",
    "                        left[key] = []\n",
    "                    left[key].append(left_cnt)\n",
    "                    break\n",
    "\n",
    "        latter = [0] * ((len(s) + 1) // 2)\n",
    "\n",
    "        for key, val in right.items():\n",
    "            left_val = left[key]\n",
    "            t = len(val)\n",
    "            for i in range(len(val)):\n",
    "                latter[val[t - i - 1] - 1] = left_val[i]\n",
    "        \n",
    "        latter.reverse()\n",
    "\n",
    "        n = len(latter)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if (latter[i] > latter[j]):\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n,ans=len(s),0\n",
    "        r,l=n-1,0\n",
    "        s=list(s)\n",
    "        while l<r:\n",
    "            flag=True\n",
    "            for k in range(r,l,-1):\n",
    "                if s[k]==s[l]:\n",
    "                    flag=False\n",
    "                    for k in range(k,r):\n",
    "                        s[k],s[k+1]=s[k+1],s[k]\n",
    "                        ans+=1\n",
    "                    r-=1\n",
    "                    break\n",
    "            if flag:ans+=n//2-l\n",
    "            l+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT1:\n",
    "    \"\"\"单点修改,区间和查询\"\"\"\n",
    "\n",
    "    __slots__ = \"size\", \"bit\", \"tree\"\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.size = n\n",
    "        self.bit = n.bit_length()\n",
    "        self.tree = [0]*(n+1)\n",
    "\n",
    "    def add(self, index: int, delta: int) -> None:\n",
    "        # index 必须大于0\n",
    "        while index <= self.size:\n",
    "            self.tree[index]+=delta\n",
    "            index += index & -index\n",
    "\n",
    "    def _query(self, index: int) -> int: \n",
    "        res = 0\n",
    "        while index > 0:\n",
    "            res += self.tree[index]\n",
    "            index -= index & -index\n",
    "        return res\n",
    "\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self._query(right) - self._query(left - 1)\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        s=s\n",
    "        idx=defaultdict(deque)\n",
    "        for i,c in enumerate(s,1):\n",
    "            idx[c].append(i)\n",
    "        res=0\n",
    "        bit=BIT1(len(s)+10)\n",
    "        for i in range(1,len(s)+1):\n",
    "            bit.add(i,1)\n",
    "        for c in s:\n",
    "            if len(idx[c])<2:\n",
    "                continue\n",
    "            i=idx[c].popleft()\n",
    "            j=idx[c].pop()\n",
    "            bit.add(i,-1)\n",
    "            bit.add(j,-1)\n",
    "            res+=bit.query(1,i)+bit.query(j,len(s)+5)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n // 2):\n",
    "            j = s.rfind(s[i])\n",
    "            if j == i:\n",
    "                ans += n // 2 - i \n",
    "                s = s[:i] + s[i+1:]\n",
    "                n -= 1\n",
    "                j = s.rfind(s[i])\n",
    "            ans += n - 1 - i - j\n",
    "            s = s[:j] + s[j+1:n-i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.array = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, idx, val):\n",
    "        idx += 1 \n",
    "        while idx < len(self.array):\n",
    "            self.array[idx] += val \n",
    "            idx += idx & (- idx)\n",
    "    \n",
    "    def query(self, idx):\n",
    "        res = 0\n",
    "        idx += 1 \n",
    "        while idx > 0:\n",
    "            res += self.array[idx]\n",
    "            idx -= idx & (- idx)\n",
    "        return res \n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = collections.defaultdict(list)\n",
    "        right = collections.defaultdict(list)\n",
    "        lidx = 0\n",
    "        ridx = 0\n",
    "        res = 0\n",
    "        counter = collections.Counter(s)\n",
    "        for i in range(n):\n",
    "            if (len(left[s[i]]) + 1) <= counter[s[i]] // 2:\n",
    "                res += i - lidx\n",
    "                left[s[i]].append(lidx)\n",
    "                lidx += 1 \n",
    "            else:\n",
    "                right[s[i]].append(ridx)\n",
    "                ridx += 1 \n",
    "        for c in counter:\n",
    "            if counter[c] % 2:\n",
    "                left[c].append(lidx)\n",
    "                lidx += 1 \n",
    "                break \n",
    "        array = [0] * (n // 2 + n % 2)\n",
    "        for c in left:\n",
    "            for l, r in zip(left[c], right[c][::-1]):\n",
    "                array[l] = r \n",
    "        bit = BIT(n // 2 + n % 2)\n",
    "        for idx in array:\n",
    "            res += bit.query(idx - 1)\n",
    "            bit.update(idx, 1)\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l,r,res = 0,n-1,0\n",
    "        while n > 1:\n",
    "            for i in range(n):\n",
    "                if s[i] == s[-1]:\n",
    "                    res += i\n",
    "                    s = s[:i] + s[i+1:n-1]\n",
    "                    n -= 2\n",
    "                    break\n",
    "                elif s[n-1-i] == s[0]:\n",
    "                    res += i\n",
    "                    s = s[1:n-1-i] + s[n-i:]\n",
    "                    n -= 2\n",
    "                    break\n",
    "        return res\n",
    "            \n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\r\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\r\n",
    "        ss = list(s)\r\n",
    "        ans = 0\r\n",
    "        l, r = 0, len(s) - 1\r\n",
    "        while l <= r:\r\n",
    "            if ss[l] != ss[r]:\r\n",
    "                lp = l + 1\r\n",
    "                while lp <= r and ss[lp] != ss[r]:\r\n",
    "                    lp += 1\r\n",
    "                rp = r - 1\r\n",
    "                while rp >= l and ss[rp] != ss[l]:\r\n",
    "                    rp -= 1\r\n",
    "                if lp - l < r - rp:\r\n",
    "                    ans += lp - l\r\n",
    "                    for i in range(lp, l, -1):\r\n",
    "                        ss[i], ss[i - 1] = ss[i - 1], ss[i]\r\n",
    "                else:\r\n",
    "                    ans += r - rp\r\n",
    "                    for i in range(rp, r):\r\n",
    "                        ss[i], ss[i + 1] = ss[i + 1], ss[i]\r\n",
    "            l += 1\r\n",
    "            r -= 1\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        # 模板：使用树状数组贪心模拟交换构建回文串\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for _ in range(n//2):\n",
    "            j = s.rindex(s[0])\n",
    "            if j == 0:\n",
    "                i = s.index(s[-1])\n",
    "                ans += i\n",
    "                s = s[:i] + s[i+1:-1]\n",
    "            else:\n",
    "                ans += len(s) - 1 - j\n",
    "                s = s[1:j] + s[j+1:]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n//2):\n",
    "            j = s.rfind(s[i])\n",
    "            if j == i:\n",
    "                ans += n // 2 - i\n",
    "                s = s[:i] + s[i+1:]\n",
    "                n -= 1\n",
    "                j = s.rfind(s[i])\n",
    "            ans += n - i - j - 1\n",
    "            s = s[:j] + s[j+1:]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = list(s)\n",
    "        ans = 0\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            if res[i] != res[j]:\n",
    "                left = right = -1\n",
    "                for k in range(i+1, j):\n",
    "                    if res[k] == res[j]:\n",
    "                        left = k\n",
    "                        break\n",
    "                for k in range(j-1, i, -1):\n",
    "                    if res[k] == res[i]:\n",
    "                        right = k\n",
    "                        break\n",
    "                if left!=-1 and (right == -1 or j-right > i-left):\n",
    "                    for k in range(left, i, -1):\n",
    "                        ans += 1\n",
    "                        res[k], res[k-1] = res[k-1], res[k]\n",
    "                else:\n",
    "                    for k in range(right, j):\n",
    "                        ans += 1\n",
    "                        res[k], res[k+1] = res[k+1], res[k]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        L = len(s)\n",
    "        s = list(s)\n",
    "        tree = [0]*(L+1)\n",
    "        res = 0\n",
    "        def holes(off):\n",
    "            res = 0\n",
    "            while off:\n",
    "                res += tree[off]\n",
    "                off &= off - 1\n",
    "            return res\n",
    "        def addHole(off):\n",
    "            while off <= L:\n",
    "                tree[off] += 1\n",
    "                off += off & -off\n",
    "        def rangeHoles(l, r):\n",
    "            l, r = min(l, r), max(l, r)\n",
    "            return holes(r) - holes(l-1)\n",
    "\n",
    "        posByC = defaultdict(deque)\n",
    "        for i, c in enumerate(s):\n",
    "            posByC[c].append(i)\n",
    "        lastOff = oddOff = -1\n",
    "        for off in range(L):\n",
    "            c = s[off]\n",
    "            if not c: continue\n",
    "            lst = posByC[c]\n",
    "            if len(lst) == 1:\n",
    "                oddOff = off\n",
    "                continue\n",
    "            lst.popleft()\n",
    "            lastOff = off\n",
    "            off = lst.pop()\n",
    "            res += L - 1 - off - rangeHoles(off+1, L)\n",
    "            s[off] = None\n",
    "            addHole(off+1)\n",
    "        if oddOff >= 0:\n",
    "            res += abs(oddOff - lastOff-1) - rangeHoles(lastOff+2, oddOff+1)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        #copy zero\n",
    "        freq = Counter(s)\n",
    "\n",
    "        ans = 0\n",
    "        left,right= defaultdict(list),defaultdict(list)\n",
    "        lcnt = rcnt =  0\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            if len(left[c]) + 1 <= freq[c]//2:\n",
    "                 lcnt += 1\n",
    "                 left[c].append(lcnt)\n",
    "                 ans += (i-lcnt+1)\n",
    "            else:\n",
    "                rcnt += 1\n",
    "                right[c].append(rcnt)\n",
    "        \n",
    "        if len(s)%2==1:\n",
    "            for c,occ in freq.items():\n",
    "                if occ%2==1:\n",
    "                    lcnt += 1\n",
    "                    left[c].append(lcnt)\n",
    "                    break\n",
    "        \n",
    "        perm = [0]*((len(s)+1)//2)\n",
    "        for c in right:\n",
    "            for x,y in zip(left[c],right[c][::-1]):\n",
    "                perm[y-1] =x\n",
    "        \n",
    "        perm = perm[::-1]\n",
    "\n",
    "        def bruteforce():\n",
    "            n = len(perm)\n",
    "            cnt =0\n",
    "            for i in range(n):\n",
    "                for j in range(i+1,n):\n",
    "                    if perm[i]>perm[j]:\n",
    "                        cnt += 1\n",
    "            return cnt\n",
    "        \n",
    "        def getbit():\n",
    "            n = len(perm)\n",
    "            tree = [0]*(n+1)\n",
    "            \n",
    "            def lowbit(x):\n",
    "                return x&(-x)\n",
    "            \n",
    "            def query(x):\n",
    "                ret = 0\n",
    "                while x>0:\n",
    "                    ret += tree[x]\n",
    "                    x -= lowbit(x)\n",
    "                return ret\n",
    "            \n",
    "            def update(x):\n",
    "                while x <= n:\n",
    "                    tree[x] += 1\n",
    "                    x+= lowbit(x)\n",
    "            \n",
    "            cnt =0 \n",
    "            for num in perm[::-1]:\n",
    "                cnt += query(num-1)\n",
    "                update(num)\n",
    "            return cnt\n",
    "        \n",
    "        return ans + getbit()\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeArrayRangeQuerySum:\n",
    "    # 模板：树状数组 单点增减 查询前缀和与区间和\n",
    "    def __init__(self, n: int) -> None:\n",
    "        # 索引从 1 到 n\n",
    "        self.t = [0] * (n + 1)\n",
    "        # 树状数组中每个位置保存的是其向前 low_bit 的区间和\n",
    "        return\n",
    "\n",
    "    def build(self, nums: List[int]) -> None:\n",
    "        # 索引从 1 开始使用数组初始化树状数组\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + nums[i]\n",
    "            self.t[i+1] = pre[i+1] - pre[i+1-self.lowest_bit(i+1)]\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def lowest_bit(i: int) -> int:\n",
    "        # 经典 low_bit 即最后一位二进制为 1 所表示的数\n",
    "        return i & (-i)\n",
    "\n",
    "    def query(self, i: int) -> int:\n",
    "        # 索引从 1 开始，查询 1 到 i 的前缀区间和\n",
    "        mi = 0\n",
    "        while i:\n",
    "            mi += self.t[i]\n",
    "            i -= self.lowest_bit(i)\n",
    "        return mi\n",
    "\n",
    "    def query_range(self, x: int, y: int) -> int:\n",
    "        # 索引从 1 开始，查询 x 到 y 的值\n",
    "        return self.query(y) - self.query(x-1)\n",
    "\n",
    "    def update(self, i: int, mi: int) -> None:\n",
    "        # 索引从 1 开始，索引 i 的值增加 mi 且 mi 可正可负\n",
    "        while i < len(self.t):\n",
    "            self.t[i] += mi\n",
    "            i += self.lowest_bit(i)\n",
    "        return\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        lst = list(s)\n",
    "        ans = 0\n",
    "        dct = defaultdict(deque)\n",
    "        for i in range(n):\n",
    "            dct[lst[i]].append(i)\n",
    "        tree = TreeArrayRangeQuerySum(n)\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            if lst[i] == \"\":\n",
    "                i += 1\n",
    "                continue\n",
    "            if lst[j] == \"\":\n",
    "                j -= 1\n",
    "                continue\n",
    "            if lst[i] == lst[j]:\n",
    "                dct[lst[i]].popleft()\n",
    "                dct[lst[j]].pop()\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                continue\n",
    "            if len(dct[lst[j]]) >= 2:\n",
    "                left = dct[lst[j]][0]\n",
    "            else:\n",
    "                left = -1\n",
    "\n",
    "            if len(dct[lst[i]]) >= 2:\n",
    "                right = dct[lst[i]][-1]\n",
    "            else:\n",
    "                right = -1\n",
    "            if left != -1 and (right == -1 or left - i - tree.query_range(i+1, left+1) <= j-right-tree.query_range(right+1, j+1)):\n",
    "                ans += left - i - tree.query_range(i+1, left+1)\n",
    "                x = dct[lst[j]].popleft()\n",
    "                dct[lst[j]].pop()\n",
    "                lst[x] = \"\"\n",
    "                tree.update(x+1, 1)\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans += j-right-tree.query_range(right+1, j+1)\n",
    "                x = dct[lst[i]].pop()\n",
    "                dct[lst[i]].popleft()\n",
    "                tree.update(x + 1, 1)\n",
    "                lst[x] = \"\"\n",
    "                i += 1\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.array = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, idx, val):\n",
    "        idx += 1 \n",
    "        while idx < len(self.array):\n",
    "            self.array[idx] += val \n",
    "            idx += idx & (- idx)\n",
    "    \n",
    "    def query(self, idx):\n",
    "        res = 0\n",
    "        idx += 1 \n",
    "        while idx > 0:\n",
    "            res += self.array[idx]\n",
    "            idx -= idx & (- idx)\n",
    "        return res \n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left = collections.defaultdict(list)\n",
    "        right = collections.defaultdict(list)\n",
    "        lidx = 0\n",
    "        ridx = 0\n",
    "        res = 0\n",
    "        counter = collections.Counter(s)\n",
    "        for i in range(n):\n",
    "            if (len(left[s[i]]) + 1) <= counter[s[i]] // 2:\n",
    "                res += i - lidx\n",
    "                left[s[i]].append(lidx)\n",
    "                lidx += 1 \n",
    "            else:\n",
    "                right[s[i]].append(ridx)\n",
    "                ridx += 1 \n",
    "        for c in counter:\n",
    "            if counter[c] % 2:\n",
    "                left[c].append(lidx)\n",
    "                lidx += 1 \n",
    "                break \n",
    "        array = [0] * (n // 2 + n % 2)\n",
    "        for c in left:\n",
    "            for l, r in zip(left[c], right[c][::-1]):\n",
    "                array[l] = r \n",
    "        bit = BIT(n // 2 + n % 2)\n",
    "        for idx in array:\n",
    "            res += bit.query(idx - 1)\n",
    "            bit.update(idx, 1)\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        # 每个字母出现的次数\n",
    "        freq = Counter(s)\n",
    "\n",
    "        ans = 0\n",
    "        # 前一半和后一半\n",
    "        left, right = defaultdict(list), defaultdict(list)\n",
    "        lcnt = rcnt = 0\n",
    "\n",
    "        # 统计「组间交换」的操作次数\n",
    "        for i, c in enumerate(s):\n",
    "            if len(left[c]) + 1 <= freq[c] // 2:\n",
    "                # 属于前一半\n",
    "                lcnt += 1\n",
    "                left[c].append(lcnt)\n",
    "                ans += (i - lcnt + 1)\n",
    "            else:\n",
    "                # 属于后一半\n",
    "                rcnt += 1\n",
    "                right[c].append(rcnt)\n",
    "        \n",
    "        # 如果长度为奇数，需要在前一半末尾添加一个中心字母\n",
    "        if len(s) % 2 == 1:\n",
    "            for c, occ in freq.items():\n",
    "                if occ % 2 == 1:\n",
    "                    lcnt += 1\n",
    "                    left[c].append(lcnt)\n",
    "                    break\n",
    "        \n",
    "        # 得到排列\n",
    "        perm = [0] * ((len(s) + 1) // 2)\n",
    "        for c in right:\n",
    "            for x, y in zip(left[c], right[c][::-1]):\n",
    "                perm[y - 1] = x\n",
    "        \n",
    "        perm = perm[::-1]\n",
    "\n",
    "        # 计算逆序对，统计「组内交换」的操作次数\n",
    "        # 暴力法\n",
    "        def get_brute_force() -> int:\n",
    "            n = len(perm)\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    if perm[i] > perm[j]:\n",
    "                        cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        # 树状数组法\n",
    "        def get_bit() -> int:\n",
    "            n = len(perm)\n",
    "            tree = [0] * (n + 1)\n",
    "            \n",
    "            def lowbit(x: int) -> int:\n",
    "                return x & (-x)\n",
    "\n",
    "            def query(x: int) -> int:\n",
    "                ret = 0\n",
    "                while x > 0:\n",
    "                    ret += tree[x]\n",
    "                    x -= lowbit(x)\n",
    "                return ret\n",
    "            \n",
    "            def update(x: int) -> None:\n",
    "                while x <= n:\n",
    "                    tree[x] += 1\n",
    "                    x += lowbit(x)\n",
    "            \n",
    "            cnt = 0\n",
    "            for num in perm[::-1]:\n",
    "                cnt += query(num - 1)\n",
    "                update(num)\n",
    "            return cnt\n",
    "\n",
    "        # return ans + get_brute_force()\n",
    "        return ans + get_bit()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeArrayRangeQuerySum:\n",
    "    # 模板：树状数组 单点增减 查询前缀和与区间和\n",
    "    def __init__(self, n: int) -> None:\n",
    "        # 索引从 1 到 n\n",
    "        self.t = [0] * (n + 1)\n",
    "        # 树状数组中每个位置保存的是其向前 low_bit 的区间和\n",
    "        return\n",
    "\n",
    "    def build(self, nums: List[int]) -> None:\n",
    "        # 索引从 1 开始使用数组初始化树状数组\n",
    "        n = len(nums)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] + nums[i]\n",
    "            self.t[i+1] = pre[i+1] - pre[i+1-self.lowest_bit(i+1)]\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def lowest_bit(i: int) -> int:\n",
    "        # 经典 low_bit 即最后一位二进制为 1 所表示的数\n",
    "        return i & (-i)\n",
    "\n",
    "    def query(self, i: int) -> int:\n",
    "        # 索引从 1 开始，查询 1 到 i 的前缀区间和\n",
    "        mi = 0\n",
    "        while i:\n",
    "            mi += self.t[i]\n",
    "            i -= self.lowest_bit(i)\n",
    "        return mi\n",
    "\n",
    "    def query_range(self, x: int, y: int) -> int:\n",
    "        # 索引从 1 开始，查询 x 到 y 的值\n",
    "        return self.query(y) - self.query(x-1)\n",
    "\n",
    "    def update(self, i: int, mi: int) -> None:\n",
    "        # 索引从 1 开始，索引 i 的值增加 mi 且 mi 可正可负\n",
    "        while i < len(self.t):\n",
    "            self.t[i] += mi\n",
    "            i += self.lowest_bit(i)\n",
    "        return\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        lst = list(s)\n",
    "        ans = 0\n",
    "        dct = defaultdict(deque)\n",
    "        for i in range(n):\n",
    "            dct[lst[i]].append(i)\n",
    "        tree = TreeArrayRangeQuerySum(n)\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            if lst[i] == \"\":\n",
    "                i += 1\n",
    "                continue\n",
    "            if lst[j] == \"\":\n",
    "                j -= 1\n",
    "                continue\n",
    "            if lst[i] == lst[j]:\n",
    "                dct[lst[i]].popleft()\n",
    "                dct[lst[j]].pop()\n",
    "                i += 1\n",
    "                j -= 1\n",
    "                continue\n",
    "            if len(dct[lst[j]]) >= 2:\n",
    "                left = dct[lst[j]][0]\n",
    "            else:\n",
    "                left = -1\n",
    "\n",
    "            if len(dct[lst[i]]) >= 2:\n",
    "                right = dct[lst[i]][-1]\n",
    "            else:\n",
    "                right = -1\n",
    "            if left != -1:\n",
    "                ans += left - i - tree.query_range(i+1, left+1)\n",
    "                x = dct[lst[j]].popleft()\n",
    "                dct[lst[j]].pop()\n",
    "                lst[x] = \"\"\n",
    "                tree.update(x+1, 1)\n",
    "                j -= 1\n",
    "            else:\n",
    "                ans += j-right-tree.query_range(right+1, j+1)\n",
    "                x = dct[lst[i]].pop()\n",
    "                dct[lst[i]].popleft()\n",
    "                tree.update(x + 1, 1)\n",
    "                lst[x] = \"\"\n",
    "                i += 1\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, t: str) -> int:\n",
    "        s = list(t)\n",
    "        n = len(s)\n",
    "        def f(l,r):\n",
    "            nonlocal s\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            if s[l] == s[r]:\n",
    "                return f(l + 1, r - 1)\n",
    "            res = 0\n",
    "            k = r - 1\n",
    "            while s[k] != s[l]:\n",
    "                k -= 1\n",
    "            if k == l:\n",
    "                return (r - l + 1) // 2 + f(l+1,r) \n",
    "            for i in range(k+1,r+1):\n",
    "                s[i],s[i-1] = s[i-1],s[i]\n",
    "                res += 1\n",
    "            \n",
    "            return res + f(l+1,r-1)\n",
    "        return f(0,n-1)\n",
    "            \n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, t: str) -> int:\n",
    "        s = list(t)\n",
    "        n = len(s)\n",
    "        def f(l,r):\n",
    "            nonlocal s\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            if s[l] == s[r]:\n",
    "                return f(l + 1, r - 1)\n",
    "            res = 0\n",
    "            k = r - 1\n",
    "            while s[k] != s[l]:\n",
    "                k -= 1\n",
    "            # 奇数的情况\n",
    "            if k == l:\n",
    "                return (r - l + 1) // 2 + f(l+1,r) \n",
    "            for i in range(k+1,r+1):\n",
    "                s[i],s[i-1] = s[i-1],s[i]\n",
    "                res += 1\n",
    "            \n",
    "            return res + f(l+1,r-1)\n",
    "        return f(0,n-1)\n",
    "            \n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        def go(s):\n",
    "            n = len(s)\n",
    "            if n <= 1:\n",
    "                return 0\n",
    "            first = s[0]    \n",
    "            for i in range(n - 1, 0, -1):\n",
    "                if first == s[i]:\n",
    "                    return n - i - 1 + go(s[1:i] + s[i+1:])\n",
    "            middle = n // 2\n",
    "            return middle + go(s[1:])\n",
    "        return go(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(s: str) -> int:\n",
    "            n = len(s)\n",
    "            if n <= 1:\n",
    "                return 0\n",
    "            for i in range(n - 1):\n",
    "                if s[i] == s[-1]:\n",
    "                    return i + dfs(s[:i] + s[i + 1 : -1])\n",
    "            for i in range(n - 1, 0, -1):\n",
    "                if s[i] == s[0]:\n",
    "                    return n - 1 - i + dfs(s[1:i] + s[i + 1 :])\n",
    "            return -1\n",
    "\n",
    "        return dfs(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToMakePalindrome(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            if s == \"\": return 0\n",
    "            for i in range(len(s)):\n",
    "                if s[-1] == s[i]:\n",
    "                    if i < len(s) - 1:\n",
    "                        return i + dfs(s[:i] + s[i + 1:-1])\n",
    "                    else:\n",
    "                        return i // 2 + dfs(s[:-1])\n",
    "        return dfs(s)\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
